我试图了解分布式计算,并遇到了一个查找大量数字中位数的问题:
假设我们有一大组数字(假设元素数量是N*K),它们不能适合内存(大小为N).我们如何找到这些数据的中位数?假设在存储器上执行的操作是独立的,即我们可以认为每个K机器最多可以处理N个元素.
我认为中位数的中位数可用于此目的.我们可以一次将N个数字加载到内存中.我们O(logN)
及时找到该集合的中位数并保存.
然后我们保存所有这些K中位数并找出中位数的中位数.此外O(logK)
,到目前为止,复杂性一直是O(K*logN + logK)
.
但这个中位数的中位数只是一个近似的中位数.我认为将它用作获得最佳案例性能的支点是最佳的,但为此我们需要将所有N*K数字拟合到内存中.
现在我们有一个很好的近似支点,我们怎样才能找到集合的实际中位数?
你为什么不建立直方图?即属于几个类别的案例(值)的数量.类别应该是变量的连续,非重叠区间.
使用此直方图,您可以首先估计中位数(即中位数在[a,b]之间),并知道有多少值落入此区间(H).如果H <= N,则再次读取数字,在此间隔之外忽略这些数字,并将间隔内的数字移至RAM.找到中位数.
如果H> N,则执行间隔的新分区并重复该过程.它不应该超过2或3次迭代.
请注意,对于每个分区,您只需要存储a,b,Delta和具有落入每个子区间的值数的数组.
编辑.它转出来比我想象的要复杂一点.在估计中位数落入的间隔后的每次迭代中,我们还应该考虑我们在该区间的右侧和左侧留下的"多少"直方图.我也改变了停止条件.无论如何,我做了一个C++实现.
#include <iostream> #include <algorithm> #include <time.h> #include <stdlib.h> //This is N^2... or just the number of values in your array, //note that we never modify it except at the end (just for sorting //and testing purposes). #define N2 1000000 //Number of elements in the histogram. Must be >2 #define HISTN 1000 double findmedian (double *values, double min, double max); int getindex (int *hist); void put (int *hist, double min, double max, double val, double delta); int main () { //Set max and min to the max/min values your array variables can hold, //calculate it, or maybe we know that they are bounded double max=1000.0; double min=0.0; double delta; double values[N2]; int hist[HISTN]; int ind; double median; int iter=0; //Initialize with random values srand ((unsigned) (time(0))); for (int i=0; i<N2; ++i) values[i]=((double)rand()/(double)RAND_MAX); double imin=min; double imax=max; clock_t begin=clock(); while (1) { iter++; for (int i=0; i<HISTN; ++i) hist[i]=0; delta=(imax-imin)/HISTN; for (int j=0; j<N2; ++j) put (hist, imin, imax, values[j], delta); ind=getindex (hist); imax=imin; imin=imin+delta*ind; imax=imax+delta*(ind+1); if (hist[ind]==1 || imax-imin<=DBL_MIN) { median=findmedian (values, imin, imax); break; } } clock_t end=clock(); std::cout << "Median with our algorithm: " << median << " - " << iter << "iterations of the algorithm" << std::endl; double time=(double)(end-begin)/CLOCKS_PER_SEC; std::cout << "Time: " << time << std::endl; //Let's compare our result with the median calculated after sorting the //array //Should be values[(int)N2/2] if N2 is odd begin=clock(); std::sort (values, values+N2); std::cout << "Median after sorting: " << values[(int)N2/2-1] << std::endl; end=clock(); time=(double)(end-begin)/CLOCKS_PER_SEC; std::cout << "Time: " << time << std::endl; return 0; } double findmedian (double *values, double min, double max) { for (int i=0; i<N2; ++i) if (values[i]>=min && values[i]<=max) return values[i]; return 0; } int getindex (int *hist) { static int pd=0; int left=0; int right=0; int i; for (int k=0; k<HISTN; k++) right+=hist[k]; for (i=0; i<HISTN; i++) { right-=hist[i]; if (i>0) left+=hist[i-1]; if (hist[i]>0) { if (pd+right-left<=hist[i]) { pd=pd+right-left; break; } } } return i; } void put (int *hist, double min, double max, double val, double delta) { int pos; if (val<min || val>max) return; pos=(val-min)/delta; hist[pos]++; return; }
为了与算法的结果进行比较,我还包括了中位数(排序)的简单计算.4或5次迭代就足够了.这意味着我们只需要从网络或硬盘读取设备4-5次.
一些结果:
N2=10000 HISTN=100 Median with our algorithm: 0.497143 - 4 iterations of the algorithm Time: 0.000787 Median after sorting: 0.497143 Time: 0.001626 (Algorithm is 2 times faster) N2=1000000 HISTN=1000 Median with our algorithm: 0.500665 - 4 iterations of the algorithm Time: 0.028874 Median after sorting: 0.500665 Time: 0.097498 (Algorithm is ~3 times faster)
如果要并行化算法,每台机器可以有N个元素并计算直方图.一旦计算出来,他们就会将它发送到主机,这将对所有直方图求和(简单,它可能非常小......算法甚至适用于2个间隔的直方图).然后它将向从机发送新指令(即新间隔)以便计算新的直方图.请注意,每台机器不需要了解其他机器拥有的N个元素.